算法设计------ AVL Tree

发表于 | 分类于 ，

写在前面

本文是在Binary Search Tree的基础上讨论构建AVL树，了解Binary Search Tree 戳我

AVL 树

定义：AVL树是具有以下性质的二叉搜索树：

  • 在AVL树中任何节点的两个子树的高度最大差值为1。
  • 插入或删除操作可能需要通过一次或多次树旋转来重新平衡这个树。

AVLTree 和二叉搜索树

AVL树相比于二叉搜索树的优势在于： 查找、插入、删除的平均和最坏时间复杂度均为O（log n）。

旋转操作

前面提到，在执行插入或删除操作后可能需要通过一次或多次树旋转来重新平衡这个树。

基本旋转操作

基本的旋转操作为左旋、右旋：

1
2
3
4
5
6
7
8
 T1, T2 和 T3是以y (左侧) 或 x (右侧)为根的子树，两棵树可以在不打破BST属性的情况下通过右旋（左旋）进行转换
                y                               x
               / \           右旋               /  \
              x   T3   – – – – – – – >        T1   y
             / \       < - - - - - - -            / \
            T1  T2           左旋                T2  T3
旋转前后树的key值均满足
      keys(T1) < key(x) < keys(T2) < key(y) < keys(T3)

代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
//左旋操作
p_AVLTree_Node leftRotation(p_AVLTree_Node root){
	//旋转操作
    p_AVLTree_Node right_Child = root -> right_Child;
    root -> right_Child = right_Child -> left_Child;
    right_Child -> left_Child  = root;
    
    //更新节点的高度
    updateHeight(root);
    updateHeight(right_Child);
    return right_Child;
}


//右旋操作
p_AVLTree_Node rightRotation(p_AVLTree_Node root){
	//旋转操作
    p_AVLTree_Node left_Child = root -> left_Child;
    root -> left_Child = left_Child -> right_Child;
    left_Child -> right_Child = root;
    
    //更新节点的高度
    updateHeight(root);
    updateHeight(left_Child);
    return left_Child;
}

case分析

以z为根节点，x、y为子节点的不平衡二叉搜索树可能有四种排列：

  1. y是z的左边孩子，x是y的左边孩子（Left Left Case）
  2. y是z的左边孩子，x是y的右边孩子（Left Right Case）
  3. y是z的右边孩子，x是y的右边孩子（Right Right Case）
  4. y是z的右边孩子，x是y的左边孩子 （Right Left Case）

对于不同的case 需要执行不同的选择操作组合来使树重新达到平衡：

Left Left Case

单次右旋z 达到平衡

1
2
3
4
5
6
7
8
T1, T2, T3 和 T4 为子树.
         z                                      y 
        / \                                   /   \
       y   T4      Right Rotate (z)          x      z
      / \          - - - - - - - - ->      /  \    /  \ 
     x   T3                               T1  T2  T3  T4
    / \
  T1   T2

Left Right Case

左旋y 右旋z达到平衡

1
2
3
4
5
6
7
8
9
T1, T2, T3 和 T4 为子树.

     z                               z                           x
    / \                            /   \                        /  \ 
   y   T4  Left Rotate (y)        x    T4  Right Rotate(z)    y      z
  / \      - - - - - - - - ->    /  \      - - - - - - - ->  / \    / \
T1   x                          y    T3                    T1  T2 T3  T4
    / \                        / \
  T2   T3                    T1   T2

Right Right Case

单次左旋达到平衡

1
2
3
4
5
6
7
8
9
T1, T2, T3 和 T4 为子树.

  z                                y
 /  \                            /   \ 
T1   y     Left Rotate(z)       z      x
    /  \   - - - - - - - ->    / \    / \
   T2   x                     T1  T2 T3  T4
       / \
     T3  T4

Right Left Case

右旋y 左旋z达到平衡

1
2
3
4
5
6
7
8
9
T1, T2, T3 和 T4 为子树.

  z                            z                            x
  / \                          / \                          /  \ 
T1   y   Right Rotate (y)    T1   x      Left Rotate(z)   z      x
    / \  - - - - - - - - ->     /  \   - - - - - - - ->  / \    / \
   x   T4                      T2   y                  T1  T2  T3  T4
  / \                              /  \
T2   T3                           T3   T4

完整代码实现

.h 文件

1
2
3
4
5
6
7
8
9
10
11
12
13
14
typedef struct avlTree_Node{
    int height;
    int memebr;
    struct avlTree_Node * left_Child;
    struct avlTree_Node * right_Child;
}AVLTree_Node, * p_AVLTree_Node;

p_AVLTree_Node newAVLNode(int member);
//插入
p_AVLTree_Node insertAVLTree(p_AVLTree_Node root,int member);
//删除
p_AVLTree_Node deleteAVLTree(p_AVLTree_Node root,int member);
//前序遍历
void preOrder (p_AVLTree_Node root);

.c 文件

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
p_AVLTree_Node newAVLNode(int member){
    p_AVLTree_Node node = malloc(sizeof(AVLTree_Node));
    if (NULL == node) {
        printf("分配内存失败");
        exit(-1);
    }
    node -> left_Child = NULL;
    node -> right_Child = NULL;
    node -> height = 1;
    node -> memebr = member;
    return node;
}

int height (p_AVLTree_Node node){
    if (node == NULL) {
        return 0;
    }
    return node -> height;
}

int max (int a, int b){
    return  (a > b)? a : b;
}

void updateHeight (p_AVLTree_Node node){
    node -> height = max( height(node -> left_Child), height(node -> right_Child)) + 1;
}

//右旋操作
p_AVLTree_Node rightRotation(p_AVLTree_Node root){
    p_AVLTree_Node left_Child = root -> left_Child;
    root -> left_Child = left_Child -> right_Child;
    left_Child -> right_Child = root;
    
    updateHeight(root);
    updateHeight(left_Child);
    return left_Child;
}

//左旋操作
p_AVLTree_Node leftRotation(p_AVLTree_Node root){
    p_AVLTree_Node right_Child = root -> right_Child;
    root -> right_Child = right_Child -> left_Child;
    right_Child -> left_Child  = root;
    
    updateHeight(root);
    updateHeight(right_Child);
    return right_Child;
}

void preOrder (p_AVLTree_Node root){
    if (root != NULL) {
        printf("%d ",root -> memebr);
        preOrder(root -> left_Child);
        preOrder(root -> right_Child);
    }
}

int getBalance(p_AVLTree_Node node){
    if (node == NULL) {
        return 0;
    }
    return height(node -> left_Child) - height(node -> right_Child);
}

p_AVLTree_Node minAVLNode(p_AVLTree_Node root){
    p_AVLTree_Node currrent = root;
    while (currrent -> left_Child) {
        currrent = currrent -> left_Child;
    }
    return currrent;
}

p_AVLTree_Node insertAVLTree(p_AVLTree_Node root,int member){
    //插入
    if (root == NULL) return newAVLNode(member);
    if (root -> memebr == member) {
        printf("Equal keys are not allowed in BST");
        return root;
    }else if(member < root -> memebr){
        root -> left_Child = insertAVLTree(root -> left_Child, member);
    }else if (member > root -> memebr){
        root -> right_Child = insertAVLTree(root -> right_Child, member);
    }

    updateHeight(root);
    
    //旋转
    int balance = getBalance(root);
    if (balance > 1 && member < root -> left_Child -> memebr) {
        return  rightRotation(root);
    }
    if (balance > 1 && member > root -> left_Child -> memebr) {
        root -> left_Child = leftRotation(root -> left_Child);
        return rightRotation(root);
    }
    if (balance < -1 && member > root -> right_Child -> memebr) {
        return leftRotation(root);
    }
    if (balance < -1 && member < root -> right_Child -> memebr) {
        root -> right_Child = rightRotation(root -> right_Child);
        return  leftRotation(root);
    }
    return root;
}

p_AVLTree_Node deleteAVLTree(p_AVLTree_Node root,int member){
    //删除
    if (root == NULL) {
        return root;
    }else if (member < root -> memebr){
        root -> left_Child = deleteAVLTree(root -> left_Child, member);
    }else if (member > root -> memebr){
        root -> right_Child = deleteAVLTree(root -> right_Child, member);
    }else{
        if (root -> left_Child == NULL) {
            p_AVLTree_Node temp = root -> right_Child;
            free(root);
            return temp;
        }else if (root -> right_Child == NULL){
            p_AVLTree_Node temp = root -> left_Child;
            free(root);
            return temp;
        }else{
            p_AVLTree_Node temp = minAVLNode(root -> right_Child);
            root -> memebr = temp -> memebr;
            free(temp);
            return root;
        }
    }
    
    updateHeight(root);
    //旋转
    int balance = getBalance(root);
    if (balance > 1 &&  root -> left_Child) {
        return  rightRotation(root);
    }
    if (balance > 1 &&  root -> right_Child) {
        root -> left_Child = leftRotation(root -> left_Child);
        return rightRotation(root);
    }
    if (balance < -1 &&  root -> right_Child ) {
        return leftRotation(root);
    }
    if (balance < -1 &&  root -> left_Child ) {
        root -> right_Child = rightRotation(root -> right_Child);
        return  leftRotation(root);
    }
    return root;
}

测试代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
void testAVLTree(){
    
    p_AVLTree_Node root = NULL;
    root = insertAVLTree(root, 9);
    root = insertAVLTree(root, 5);
    root = insertAVLTree(root, 10);
    root = insertAVLTree(root, 0);
    root = insertAVLTree(root, 6);
    root = insertAVLTree(root, 11);
    root = insertAVLTree(root, -1);
    root = insertAVLTree(root, 1);
    root = insertAVLTree(root, 2);
    
    /* The constructed AVL Tree would be
     9
     /  \
     1    10
     /  \     \
     0    5     11
     /    /  \
     -1   2    6
     */
    printf("Preorder traversal of the constructed AVL "
           "tree is \n");

    preOrder(root);

    root = deleteAVLTree(root, 10);

    /* The AVL Tree after deletion of 10
     1
     /  \
     0    9
     /     /  \
     -1    5     11
     /  \
     2    6
     */
    printf("\nPreorder traversal after deletion of 10 \n");
    preOrder(root);
}

代码输出

1
2
3
4
Preorder traversal of the constructed AVL tree is 
9 1 0 -1 5 2 6 10 11 
Preorder traversal after deletion of 10 
1 0 -1 9 5 2 6 11

如果对你有帮助的话，Star✨下一吧！